package com.example.array.doublepointer;

/**
 * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
 *  不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 *
 *  示例 1：
 * 输入：nums = [1,1,1,2,2,3]
 * 输出：5, nums = [1,1,2,2,3]
 * 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
 *
 *  示例 2：
 * 输入：nums = [0,0,1,1,1,1,2,3,3]
 * 输出：7, nums = [0,0,1,1,2,3,3]
 * 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
 */
public class Leetcode80_RemoveDuplicates2 {
    public static void main(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 1, 2, 3, 3};
        int res = new Solution().removeDuplicates(nums);

        for (int i = 0; i < res; i++) {
            System.out.println(nums[i]);
        }

    }

    static class Solution {
        /**
         * 双指针法:
         * 因为给定数组是有序的，所以相同元素必然连续,当数组 nums 的长度大于 0时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，
         *
         * 因此 nums[0],nums[1] 保持原状即可，从下标 2 开始删除重复元素。
         * 定义两个指针 slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度
         * 两个指针都初始化为2
         * 因为要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums[slow−2] 是否和当前待检查元素 nums[fast] 相同。
         * 当且仅当 nums[slow−2]=nums[fast] 时，当前待检查元素 nums[fast] 不应该被保留（因为此时必然有 nums[slow−2]=nums[slow−1]=nums[fast]）。
         * 最后，slow 即为处理好的数组的长度。
         *
         * @param nums
         * @return
         */
        private int removeDuplicates2(int[] nums) {
            // 数组的前两个数必然可以被保留，因此对于长度不超过 2 的数组，直接返回即可
            if (nums.length <= 2) return nums.length;
            int slow = 2, fast = 2;

            // 0, 0, 1, 1, 1, 1, 2, 3, 3
            while (fast < nums.length) {
                if (nums[slow - 2] != nums[fast]) {
                    nums[slow++] = nums[fast];
                }
                fast++;
            }

            return slow;
        }

        /**
         * 暴力法
         * 设一个计数器count = 1,当count > 2时开始将后面的元素向前移
         * 遍历数组，比较相邻两个元素，如果相同就count++,然后判断count否大于2,大于2就将数组后面的所有元素向前移动一位
         * 邻两个元素不同count置为1继续向后遍历
         * @param nums
         * @return
         */
        private int removeDuplicates1(int[] nums) {
            int numLen = nums.length;
            int count = 1;
            int i = 0;
            while (i < numLen - 1) {
                if (nums[i] == nums[i + 1]) {
                    if (++count > 2) {
                        for (int j = i + 1; j < numLen - 1; j++) {
                            nums[j] = nums[j + 1];
                        }
                        numLen--;
                    } else {
                        i++;
                    }
                } else {
                    count = 1;
                    i++;
                }
            }

            return numLen;
        }

        public int removeDuplicates(int[] nums) {
            return removeDuplicates2(nums);
        }
    }
}
